package 双指针系列;
import java.util.*;

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();    //存放结果
        Arrays.sort(nums);
        //排序之后方便用双指针

        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                break;  //如果i>0;则后面的都>0，不可能存在和为0
            }
            //正确去重方法，三元组a去重
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            // 错误去重方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;   //如果采用这种方法，会让第一个-1给略过，这样的话就只剩-1，2，就会漏掉-1,-1,-2这种情况
            }
            */

            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if(nums[i] + nums[left] + nums[right] < 0 ){
                    left++;
                }else if(nums[i] + nums[left] + nums[right] > 0 ){
                    right--;
                }else{
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));

                    while(right > left && nums[left]==nums[left+1]){
                        //这里去的是left的重复元素，为啥上面去重是nums[i-1]=nums[i],这里却是nums[left]==nums[left+1]呢
                        //因为如果初始时即left=i+1时，用的是nums[left]==nums[left-1]的判定条件，恰好nums[left]和nums[i]相等，则left可能会错误的往前走一格，导致可能错过了一个元组，
                        // 举例：【-2，-2，1，1】 即nums[i]=-2,nums[left]=-2,nums[right]=4时，则去重left++再加上下面的left++，会忽略了[-2,1,1]这个三元组
                        left++;
                    }
                    //同理
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }

        }
        return  result;

    }
}
